// https://leetcode.cn/problems/combination-sum-ii/
// Created by ade on 2022/9/9.
// candidates 中的每个数字在每个组合中只能使用 一次 。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector <vector<int>> res = {};
    int len = 0;

    vector <vector<int>> combinationSum2(vector<int> &candidates, int target) {
        len = candidates.size();
        sort(candidates.begin(), candidates.end());
        for (int i = 0; i < len; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1]) continue;
            vector<int> tmp = {candidates[i]};
            dfs(tmp, candidates, i, target - candidates[i]);
        }
        return res;
    }

    void dfs(vector<int> &tmp, vector<int> &candidates, int index, int target) {
        if (target < 0) return;
        if (target == 0) {
            res.push_back(tmp);
            return;
        }
        for (int i = index + 1; i < len; i++) {
            if (target - candidates[i] < 0) break;
            target -= candidates[i];
            tmp.push_back(candidates[i]);
            dfs(tmp, candidates, i, target);
            target += candidates[i];
            tmp.pop_back();
            // 虽然这步到现在还不是很理解，但是确实有用
            while (i < len - 1 && candidates[i] == candidates[i + 1]) {
                i++;
            }
        }
    }
};

int main() {
    Solution so;
    vector<int> nums = {4, 2, 5, 2, 5, 3, 1, 5, 2, 2};
    int target = 9;
    auto res = so.combinationSum2(nums, target);
    for (auto items: res) {
        for (auto i:items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}